﻿#include <stdio.h>
#include <stdlib.h>
#include <iostream>

typedef unsigned long long ULONG64;
#define ULONG64_MAX 0xffffffffffffffff

/**
 * N皇后问题的位运算解法，使用位运算，可以降低时间复杂度的常数项，在N不是很大的时候，效果很明显。
 * @param limit n位标记，8位就是 0b11111111（0xff）, 14位就是0b11111111111111（0x3fff）
 * @param colLimit 位限制，比如上一行的第X列放过一个皇后，则对应的这一位就是1，表示这一行的这位不能放皇后了
 * @param leftDiaLimit ↙方向限制，比如，8位, 上一行这个位置放了皇后
 *                     0b00001000，
 *               则本行 0b00010000 不能放置皇后
 * @param rightDiaLimit ↘方向限制，比如，8位, 上一行这个位置放了皇后
 *      *                     0b00001000，
 *      *               则本行 0b00000100 不能放置皇后
 * @return
 */
static int process(ULONG64 limit, ULONG64 valueLimit, ULONG64 leftDownLimit, ULONG64 rightDownLimit)
{
    if (valueLimit == limit) return 1;

    ULONG64 valid = limit & (~(valueLimit | leftDownLimit | rightDownLimit));
    int total = 0;
    while (valid != 0)
    {
        ULONG64 mostRight = valid & (~valid + 1);
        total += process(limit, valueLimit | mostRight, (leftDownLimit << 1) | (mostRight << 1),  (rightDownLimit >> 1) | (mostRight >> 1));

        valid &= ~mostRight;
    }

    return total;
}

static int start(int n)
{
    if (n < 1 || n > 64)
    {
        printf("Not support: N = %d\n", n);
        return 0;
    }

    ULONG64 limitN = 1ULL << n;
    limitN -= 1;
    ULONG64 limit = n == 64 ? ULONG64_MAX : limitN;
    int methodCount = process(limit, 0, 0, 0);
    return methodCount;
}

/**
 * N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行，不同列，也不在同一条斜线上。
 * 给定一个整数n，返回n皇后的摆法有多少种。
 * n=1, 返回1
 * n=2或3, 2皇后和3皇后问题无论怎么摆都不行，返回0
 * n=8, 返回92.
 *
 * 基本思路：暴力递归
 */
int main_NQueen()
{
    int total = start(8);
    printf("method count=%d\n", total);
    return 0;
}